package version2024.medium;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ24 合唱队  动态规划
 * @Date: created in 2024/12/28 星期六 15:57
 * @Modified By:
 */
public class HJ24_Chorus {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            // 读取人数
            int n = in.nextInt();
            // 根据人数构建身高数组
            int[] arr = new int[n];
            // 读取身高
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }

            // 186 186 150 200 160 130 197 200
            // dpLeft
            //  0   1   2   3   4   5   6   7
            //  1   1   1   2   2   1   3   4
            // dpRight
            //  0   1   2   3   4   5   6   7
            //  3   3   2   3   2   1   1   1
            // dp数组的定义: dp[i]保存的是小于等于arr[i]的元素的数量
            // 从左到右, 保存满足每个数最长递增子序列的序列长度的dp数组
            int[] left = new int[n];
            // baseCase 包含数字自己
            Arrays.fill(left, 1);
            // 从右到左, 保存满足每个数最长递增子序列的序列长度的dp数组
            int[] right = new int[n];
            Arrays.fill(right, 1);

            // 计算从左到右的最长子序列长度
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (arr[i] > arr[j]) {
                        // 因为baseCase为1, 所以这里是统计了i本身的, 故为小于等于
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }

            // 计算从右到左的最长子序列长度
            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j > i; j--) {
                    if (arr[i] > arr[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }

            // 结果的汇总, 两个单向dp数组, 汇总出左右两边均小于等于arr[i]元素的数量
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                // 位置i被计算了两次, 要-1
                result[i] = left[i] + right[i] - 1;
            }

            // 找到最大的满足要求的值
            int max = 1;
            for (int i = 0; i < n; i++) {
                max = Math.max(max, result[i]);
            }
            // 总人数-最大的满足要求的值, 即需要出列人数
            System.out.println(n - max);
        }
    }
}
